#include "emparelhamento.h"

Emparelhamento::Emparelhamento(Grafo *grf, int tipo){
  
  grafo = grf;
  
  n = grf->adj.size();
  
  tipoEmp = tipo;
  
}


int Emparelhamento::mapeia(int *mapaIda, vector<int> **mapaVolta){
  
  int nV;
  
  nV = mapeiaAleatorio(mapaIda, mapaVolta);
  
  return nV;
}

int Emparelhamento::mapeiaAleatorio(int *mapaIda, vector<int> **mapaVolta){
    
  //Constroi mapaIda == encontra um emparelhamento maximal
  
  int i;
  int candVistos = 0;

  int adjTotal;
  int adjVistos = 0;

  int iAdj;
  int vAtual = 0;

  int m[n]; //vetor de marcacao

  for(int i = 0; i < n; ++i)
    mapaIda[i] = -1;			//vertice i não foi emparelhado


  while(candVistos != n){

    i = rand()%n;			//escolhe alguém aleatoriamente

    if(mapaIda[i] != -1) continue;

    mapaIda[i] = vAtual;
    candVistos ++;

    //printf("%d ", i);

    adjTotal = (*grafo).adj[i].size();
    adjVistos = 0;

    memset(m, 0, sizeof(m));

    while(adjVistos != adjTotal){	//ve se tem algum candidato aleatorio para emparelhar com i

      iAdj = rand()%adjTotal;

      if(mapaIda[(*grafo).adj[i][iAdj].v] == -1 && (*grafo).vPeso[i] + (*grafo).vPeso[(*grafo).adj[i][iAdj].v] <= (*grafo).pesoMax){

	mapaIda[(*grafo).adj[i][iAdj].v] = vAtual;
	candVistos ++;
	
//	printf("%d", adj[i][iAdj].v);
	break;
	
      }else{

	if(m[iAdj] == 0){
	  m[iAdj] = 1;
	  adjVistos ++;
	}
      }

    }
    //printf("\n");
    
    vAtual ++;
  
  }
  
  //constroi mapaVolta
  
  int nV = vAtual;
  
  //vector<int> mapaVolta[nV]; -- queria q o mapaVolta fosse isso

  *mapaVolta = new vector<int>[nV];
  
  //constroi o mapa dos vertices
  for(int i = 0; i < n; ++i){
    (*mapaVolta)[mapaIda[i]].push_back(i);
  } 

  return nV;
}

